package team13;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;

import edu.uci.ics.jung.graph.Graph;

public class RoleFinder {
	private GraphHolder graphHolder;
	private Graph<Node, Edge> graph;
	private ArrayList<ArrayList<Integer>> clusterList;
	
	//brute-force
	private ArrayList<Node> degreeSortList;
	private ArrayList<Node> blockList;
	private ArrayList<Node> timeList;
	private HashSet<Node> movieSet;
	
	public RoleFinder(GraphHolder graphHolder){
		this.graphHolder = graphHolder;
	}
	
	public void findRole(int startIndex){
		graph = graphHolder.getGraph();
		
		degreeSortList = new ArrayList<Node>(graph.getVertices());
		
		timeList = new ArrayList<Node>();
		movieSet = new HashSet<Node>();
		
		Collections.sort(degreeSortList, new Comparator<Node>(){
			@Override
			public int compare(Node o1, Node o2) {
				//sort in decending order
				return RoleFinder.this.graph.degree(o2) - RoleFinder.this.graph.degree(o1);
			}
		});
		
		//block the high degree nodes from movie candidate
		blockList = new ArrayList<Node>();
		for(int i = 0; i < startIndex; i++){
			blockList.add(degreeSortList.get(i));
		}
		
		int result = tryLevel(1, startIndex);
		
		if(result == 1){
			System.out.println("found!!");
			System.out.println("remake: " + countRemakeNode());
			
			int max = 0;
			Node maxMovie = null;
			for(Node movie: movieSet){
				int counter = 0;
				for(Node neighbor: graph.getNeighbors(movie)){
					if(movieSet.contains(neighbor)){
						counter++;
					}
				}
				if(counter > max){
					max = counter;
					maxMovie = movie;
				}
			}
			System.out.println("maxMovie: " + degreeSortList.indexOf(maxMovie) + " max: " + max);
			
			try {
				BufferedWriter out = new BufferedWriter(new FileWriter("time_movie_" + startIndex + "_highBlockRemake"));
				out.write("time:\n");
				for(Node node: timeList){
					out.write(node.getId() + " ");
				}
				out.newLine();
				out.write("movie:\n");
				for(Node node: movieSet){
					out.write(node.getId() + " ");
				}
				out.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}else{
			System.out.println("not found");
		}
	}
	
	public ArrayList<ArrayList<Integer>> getClusterList(){
		return clusterList;
	}
	
	private int tryLevel(int level, int startIndex){
		int movingStartIndex = startIndex;
		
		if(movieSet.size() > 11501){
			return -1;
		}
		
		while(movingStartIndex < degreeSortList.size()){
			//log////////////
			if(level < 100){
				for(int i = 1; i < level; i++){
					System.out.print(" ");
				}
				System.out.println("level: " + level + " index: " + movingStartIndex);
			}
			/////////////////
			
			int next = 0;
			next = findNextFrom(movingStartIndex);
			
			if(next < 0){
				return -1;
			}else if(movieSet.size() + (101 - level) * graph.degree(degreeSortList.get(next)) < 11501){
				return -1;
			}else{
				addToTime(next);
				
				int result = 0;
				
				if(level < 100){
					result = tryLevel(level + 1, next + 1);
				}else{
					if(movieSet.size() == 11501){
						result = 1;
					}else{
						result = -1;
					}
				}
				
				if(result == 1){
					return 1;
				}else{
					removeFromTime(next);
					movingStartIndex = next + 1;
				}
			}
		}
		return -1;
		
	}
	
	private int countRemakeNode(){
		int counter = 0;
		for(Node movie: movieSet){
			for(Node neighbor: graph.getNeighbors(movie)){
				if(movieSet.contains(neighbor)){
					counter++;
					break;
				}
			}
		}
		return counter;
	}
	
	private void addToTime(int index){
		Node time = degreeSortList.get(index);
		
		timeList.add(time);
		movieSet.addAll(graph.getNeighbors(time));
		
		for(Node neighbor: graph.getNeighbors(time)){
			neighbor.setNumOfTime(neighbor.getNumOfTime() + 1);
		}
	}
	
	private void removeFromTime(int index){
		Node time = degreeSortList.get(index);
		
		timeList.remove(time);
		
		for(Node neighbor: graph.getNeighbors(time)){
			neighbor.setNumOfTime(neighbor.getNumOfTime() - 1);
			if(neighbor.getNumOfTime() == 0){
				movieSet.remove(neighbor);
			}
		}
	}
	
	private int findNextFrom(int index){
		Node time = null;
		for(int i = index; i < degreeSortList.size(); i++){
			time = degreeSortList.get(i);
			if(!movieSet.contains(time)){
				boolean isCandidate = true;
				for(Node movie: graph.getNeighbors(time)){
					if(blockList.contains(movie)){
						isCandidate = false;
					}
					//filter out high-remake movies
					int remakeCounter = 0;
					for(Node neighbor: graph.getNeighbors(movie)){
						if(movieSet.contains(neighbor)){
							remakeCounter++;
						}
					}
					if(remakeCounter > 20){ //manually adjust the remake degree
						isCandidate = false;
					}
				}
				if(isCandidate){
					return i;
				}
			}
		}
		return -1;
	}
	
}
